package offer.zixing.chapter02;

/**
 * 排序数组中两个数字之和
 *
 * 输入一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？
 * 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
 * 例如输入数组[1, 2, 4, 6, 10]，k的值为8，数组中的数字2和6的和为8，它们的下标分别为1和3。
 */
public class Test006 {
    public static void main(String[] args) {
        int result[] = twoSum(new int[]{1, 2, 4, 6, 10}, 10);
        for (int res : result) {
            System.out.print(res + ",");
        }
    }

    public static int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        // numbers 是递增数组，可以双指针左右逼近的方式处理
        // i < j 保证左右指针永远在左边或右边
        // numbers[i] + numbers[j] != target 逆向思维，只有在不满足的条件下才进行指针移动
        while (i < j && numbers[i] + numbers[j] != target) {
            // 和小于目标值则移动左指针
            if (numbers[i] + numbers[j] < target) {
                i++;
            } else { // 反之移动右指针
                j--;
            }
        }
        return new int[]{i, j};
    }
}
